|
In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.〔.〕 traces the use of gadgets to a 1954 paper in graph theory by W. T. Tutte, in which Tutte provided gadgets for reducing the problem of finding a subgraph with given degree constraints to a perfect matching problem. However, the "gadget" terminology has a later origin, and does not appear in Tutte's paper.〔.〕〔.〕 ==Example== Many NP-completeness proofs are based on many-one reductions from 3-satisfiability, the problem of finding a satisfying assignment to a Boolean formula that is a conjunction (Boolean and) of clauses, each clause being the disjunction (Boolean or) of three terms, and each term being a Boolean variable or its negation. A reduction from this problem to a hard problem on undirected graphs, such as the Hamiltonian cycle problem or graph coloring, would typically be based on gadgets in the form of subgraphs that simulate the behavior of the variables and clauses of a given 3-satisfiability instance. These gadgets would then be glued together to form a single graph, a hard instance for the graph problem in consideration.〔.〕 For instance, the problem of testing 3-colorability of graphs may be proven NP-complete by a reduction from 3-satisfiability of this type. The reduction uses two special graph vertices, labeled as "Ground" and "False", that are not part of any gadget. As shown in the figure, the gadget for a variable ''x'' consists of two vertices connected in a triangle with the ground vertex; one of the two vertices of the gadget is labeled with ''x'' and the other is labeled with the negation of ''x''. The gadget for a clause consists of six vertices, connected to each other, to the vertices representing the terms ''t''0, ''t''1, and ''t''2, and to the ground and false vertices by the edges shown. Any 3-CNF formula may be converted into a graph by constructing a separate gadget for each of its variables and clauses and connecting them as shown.〔This reduction is described in .〕 In any 3-coloring of the resulting graph, one may designate the three colors as being true, false, or ground, where false and ground are the colors given to the false and ground vertices (necessarily different, as these vertices are made adjacent by the construction) and true is the remaining color not used by either of these vertices. Within a variable gadget, only two colorings are possible: the vertex labeled with the variable must be colored either true or false, and the vertex labeled with the variable's negation must correspondingly be colored either false or true. In this way, valid assignments of colors to the variable gadgets correspond one-for-one with truth assignments to the variables: the behavior of the gadget with respect to coloring simulates the behavior of a variable with respect to truth assignment. Each clause assignment has a valid 3-coloring if at least one of its adjacent term vertices is colored true, and cannot be 3-colored if all of its adjacent term vertices are colored false. In this way, the clause gadget can be colored if and only if the corresponding truth assignment satisfies the clause, so again the behavior of the gadget simulates the behavior of a clause. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Gadget (computer science)」の詳細全文を読む スポンサード リンク
|